Session 4 : Exercises

For any graph, an optimal flow can be computed as the solution to the convex program
min  (∑_e)(Subscript[x, e])(Subscript[c, e])((Subscript[x, e]))
     s.t.  x  is   s-t   flow
A Wardrop can be computed by solving 
min  (∑_e)∫(Subscript[c, e])((Subscript[x, e]))
     s.t.  x  is   s-t   flow
We want to set up these convex programs for any given graph with affine cost functions, to solve them later.

Exercise 1

Create the following graph g using Graph[ ]. The numbers on the edges are edge weights.
Then compute the shortest 1-v-path for all vertices v (use All in the shortest path function) and use HighlightGraph[ g , DirectedGraph[ PathGraph[ path ]] ] to highlight the shortest path in the graph

g= Graph[ (* .... *) ];
pathfunction = FindShortestPath[g, 1, All];
(* .... *)

Solution

g = Graph[{1->2,1->3,2->3,2->6,3->4,1->5,2->5,6->3,4->6,5->7,7->6}, VertexLabels->Automatic, EdgeWeight->{2,1,4,3,2,0,4,1,3,1,3},EdgeLabels->"EdgeWeight"]
pathfunc=FindShortestPath[g,1,All];
Manipulate[HighlightGraph[g,DirectedGraph[PathGraph[pathfunc[target]]]],{target,1,7,1}]

Exercise 2

Assume you are given a graph, lists of coefficients of the affine cost functions of the edges, and specified source and sink vertices, e.g., the Braess Graph:

(* Graph *)
graph = Graph[{s->v,s->w,v->w,v->t,w->t}];
(* Slopes of affine linear cost functions *)
a={1,0,0,0,1};
(* Offsets of affine linear cost functions *)
b={0,1,0,1,0};

source = s;
sink = t;

a)

For later use, we need variables “vertices”, “edges”, “n”, “m”, “sourceIndex”, “sinkIndex”, that store the list of vertices, edges of g, the number of vertices, the number of edges n and m, as well as the index of the source and the sink index. (Use the function FirstPosition[ ] to obtain the position of an element in a list, see also the documentation).
Further, we are going to need the Incidence-Matrix of the graph, store it in a variable Γ. To create a Gamma-Letter, enter [ESC] Gamma  [ESC].

Solution

vertices=VertexList[graph];
edges = EdgeList[graph];
sourceIndex=FirstPosition[vertices,source][[1]];
sinkIndex=FirstPosition[vertices,sink][[1]];
n=VertexCount[graph];
m=EdgeCount[graph];

Γ=IncidenceMatrix[graph];

b)

Create functions that take an edge index e and a flow x and compute the (affine) costs of edge e, where the cost functions are given by the coefficients a and b above, i.e., (Subscript[c, e])(x)=(Subscript[a, e])x+(Subscript[b, e]).
Create the integrated cost functions, i.e., (Subscript[(OverTilde[c]), e])(x)=((∫_0)^x)(Subscript[c, e])(t)dt. (You may use the function Integrate[ ])
Finally, create a graph that has the cost functions as EdgeLabels. To do so, you may first create a list that contains rules of the form edge -> cost(edge, x) and assign it to the option EdgeLabels. The output for the Braess graph given above should look something like

Solution

(* Create cost functions *)
c[e_,x_]:=a[[e]]*x+b[[e]];
(* Create itegrated cost functios *)
cInt[e_,x_]:=Integrate[c[e,ξ],ξ]/.ξ->x;

(* Print Graph with cost functions *)
Print["Input Graph with cost functions:"];
edgelabels=Table[ edges[[e]]->c[e,x], {e,1,m} ];
Graph[graph,VertexLabels->Automatic,EdgeLabels->edgelabels]

c)

We now want to set up the convex program to compute the Wardrop Equilibrium. We first create a list of flow variables:

(* Create list of flow-variables for the convex program *)
flowvars = Table[f[e],{e,1,m}];

Create three variables objective, flowconditions, and nonnegconditions that contain the objective function, and lists of flow conservation and non-negativity conditions.
For the objective, use the function for integrated cost from b), and use Total[ list ] to create the sum of an appropriate list.
The flow conservation states that the excess (sum of incoming minus outgoing flow) is zero (or +/- r at the sink/source). The vector of all vertex excess values can be computed by multiplying the incidence matrix Γ with the flow vector (in this case the vector of flow variables). Use the excess vector obtained this way to set up a list of flow conservation constraints (use Table[ ... ])
The non-negativity constraints can be constructed as a list containing flowvars[e] >= 0 for every edge e.

Finally, execute the following code that should produce the following output for the Braess graph above.

(* Print the conxex program *)
Print["Convex program:"];
Print[" min ",objective];
For[i=1,i≤n,i++,
praefix=If[i==1," s.t. ", "      "];
Print[praefix, flowconditions[[i]]];
];
For[i=1,i≤m,i++,
Print["      ", nonnegconditions[[i]]];
];

Solution

(* Create list of flow-variables for the convex program *)
flowvars = Table[f[e],{e,1,m}];

(* Create the objective function == Sum over all iterated cost functios *)
objective=Total[Table[ cInt[e,flowvars[[e]]], {e,1,m} ]];
(* Create flow conditions, i.e, excess = -r / +r / 0 for v = s / t / otherwise *)
(* -> Compute the excess vector containing the excess of all vertices depending on the flow definded by flowvars *)
excess=Γ.flowvars;
(* -> Create a list of flow conservation rules *)
flowconditions=Table[ excess[[v]]==If[v==sourceIndex,-r,If[v==sinkIndex,r,0]] ,{v,1,n}];

(* Create non-negativity constraints f[e]≥0 *)
nonnegconditions=Table[ flowvars[[e]]≥0, {e,1,m} ];

(* Print the conxex program *)
Print["Convex program:"];
Print[" min ",objective];
For[i=1,i≤n,i++,
praefix=If[i==1," s.t. ", "      "];
Print[praefix, flowconditions[[i]]];
];
For[i=1,i≤m,i++,
Print["      ", nonnegconditions[[i]]];
];